package com.lihepeng.leecode.solid_aim_offer.linkedlist;

import com.lihepeng.leecode.linkedList.ListNode;
import org.junit.Test;

/**
 * 描述
 * 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5  处理后为 1->2->5
 *
 * 数据范围：链表长度满足 0 \le n \le 1000 \0≤n≤1000  ，链表中的值满足 1 \le val \le 1000 \1≤val≤1000
 *
 * 进阶：空间复杂度 O(n)\O(n)  ，时间复杂度 O(n) \O(n)
 *
 * 例如输入{1,2,3,3,4,4,5}时，对应的输出为{1,2,5}，对应的输入输出链表如下图所示：
 */
public class Solution76 {

    /**
     * 删除重复节点数据
     * @param pHead
     * @return
     */
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode dumpyNode = new ListNode(-1);
        dumpyNode.next = pHead;
        ListNode header = dumpyNode;
        while (header.next !=null && header.next.next!=null) {
            if (header.next.value == header.next.next.value) {
                int temp = header.next.value;
                // 在下面寻找节点值相同的节点，直接跳过
                if (header.next!=null && header.next.value ==temp) {
                    // 删除当前节点
                    header.next = header.next.next;
                }
            }else {
                header = header.next;
            }

        }
        return dumpyNode.next;
    }
    @Test
    public void runTest() {
        ListNode head = new ListNode(0);
        ListNode head1 = new ListNode(1);
        ListNode head2 = new ListNode(1);
        ListNode head3 = new ListNode(3);
        ListNode head4 = new ListNode(4);
        ListNode head5 = new ListNode(5);
        head.next = head1;
        head1.next = head2;
        head2.next = head3;
        head3.next = head4;
        head4.next = head5;
        ListNode listNode = deleteDuplication(head);
        while (listNode!=null) {
            System.out.println(listNode.value);
            System.out.println("-->");
            listNode = listNode.next;
        }
    }
}
